/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */
typedef struct Node Node;
Node* BuyNode(int x)
{
    Node* newnode = (Node*)malloc(sizeof(Node));
    newnode->val = x;
    newnode->next = NULL;
    newnode->random = NULL;
    return newnode;
}
void AddNode(Node* phead)
{
    Node* pcur = phead;
    while (pcur)
    {
        Node* copy = BuyNode(pcur->val);
        copy->next = pcur->next;
        pcur->next = copy;
        pcur = copy->next;
    }
}
void RandomNode(Node* phead)
{
    Node* pcur = phead;
    Node* copy = phead->next;
    while (pcur)
    {
        if (pcur->random == NULL)
            copy->random = NULL;
        else
        {
            copy->random = pcur->random->next;
        }
        if (copy->next == NULL)
            break;
        pcur = copy->next;
        copy = pcur->next;
    }
}
Node* CopyLink(Node* phead)
{
    Node* pcur = phead;
    Node* copyhead = pcur->next;
    Node* copytail = copyhead;
    while (pcur)
    {
        if (copytail->next == NULL)
            break;
        pcur = copytail->next;
        copytail->next = pcur->next;
        copytail = copytail->next;
    }
    return copyhead;
}
struct Node* copyRandomList(struct Node* head) {
    if (head == NULL)
        return NULL;
    AddNode(head);
    RandomNode(head);
    Node* ret = CopyLink(head);
    return ret;
}